763. Partition Labels

Question

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

Example 1:

Input: s = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part.
A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.

Example 2:

Input: s = "eccbbbbdec"
Output: [10]

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

---

Approach

1. Iterate through the string, and save the last occurence index of each characters in a length 26 vector. 'a' will be in index 0, and so on.
2. Iterate the string again, check the last occurence index of the character.
3. If the current index is indeed the last occurence, it is the end of partition.
4. Push the current index - 1 to result vector.
5. Update start so that we know the start index of the next partition.

Solution

class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> end_idx(26,0);
        
        for(int i = 0; i < s.length(); ++i)
            end_idx[s[i] - 'a']  = i;
        
        vector<int> res;
        
        int start = 0, end = 0;
        // scanning string character by character
        for(int i = 0; i < s.length(); ++i)
        {
        // whenever we get an character we check,
        // last index of that character
            end = max(end, end_idx[s[i] - 'a']);
            
            // when current i.e i == end
            // add it to result
            if( i == end)
            {
                // all the characters of current partition included
                res.push_back(i - start + 1);
                // update the start pointer for fresh start
                start = i + 1;
            }
        }
        
        return res;
    }
};